package algorithm;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree {

    public static class Node {
        public int value;
        public Node left;
        public Node right;
        public Node parent;
        public Node (int value){
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }

        //先序递归
        public static void pre(Node head){
            if(head == null){
                return ;
            }
            System.out.println(head);
            pre(head.left);
            pre(head.right);
        }

        //中序递归
        public static void in(Node head){
            if(head == null){
                return ;
            }
            in(head.left);
            System.out.println(head);
            in(head.right);
        }

        //后序递归
        public static void pos(Node head){
            if(head == null){
                return ;
            }
            pos(head.left);
            pos(head.right);
            System.out.println(head);
        }

        //先序非递归
        public static void pre2(Node head) {
            if(head == null)
                return;
            Stack<Node> stack = new Stack<>();
            stack.push(head);
            while(!stack.isEmpty()){
                Node pop = stack.pop();
                System.out.println(pop);
                if(pop.right != null)
                    stack.push(pop.right);
                if(pop.left != null)
                    stack.push(pop.left);
            }

        }

        //后序非递归（根据先序变化出来的）
        public static void pos2(Node head) {
            if(head == null)
                return;
            Stack<Node> stack1 = new Stack<>();
            Stack<Node> stack2 = new Stack<>();
            stack1.push(head);
            while(!stack1.isEmpty()){
                Node pop = stack1.pop();
                stack2.push(pop);
                if(pop.left != null)
                    stack1.push(pop.left);
                if(pop.right != null)
                    stack1.push(pop.right);
            }
            while(!stack2.isEmpty()){
                System.out.println(stack2.pop());
            }
        }

        //后序非递归
        public static void pos3(Node head){
            if(head == null)
                return;
            Stack<Node> stack = new Stack<>();
            stack.push(head);
            Node h = head;
            Node c = null;
            while(!stack.isEmpty()){
                c = stack.peek();
                if(c.left != null && c.left != h && c.right != h){
                    stack.push(c.left);
                }else
                    if(c.right != null && c.right != h){
                        stack.push(c.right);
                    }else{
                        System.out.println(stack.pop());
                        h = c;
                    }
            }
        }

        //中序非递归
        public static void in2(Node head){
            if(head == null)
                return;
            Node index = head;
            Stack<Node> stack = new Stack<>();
            stack.push(head);
            while(!stack.isEmpty()){
                Node peek = stack.peek();
                while(peek.left != null){
                    stack.push(peek.left);
                    peek = peek.left;
                }
                Node pop = stack.pop();
                System.out.println(pop);
                if(pop.right != null)
                    stack.push(pop.right);
                else
                    if(!stack.isEmpty()){
                        Node pop1 = stack.pop();
                        System.out.println(pop1);
                        stack.push(pop1.right);
                    }

            }
        }

        //中序非递归
        public static void in3(Node head){
            if(head == null)
                return;
            Stack<Node> stack = new Stack<>();
            while(!stack.isEmpty() || head != null){
                if(head != null){
                    stack.push(head);
                    head = head.left;
                }else{
                    head = stack.pop();
                    System.out.println(head);
                    head = head.right;
                }
            }
        }

        //层次遍历
        public static void level(Node head) {
            if(head == null)
                return;
            Queue<Node> queue = new LinkedList<>();
            queue.add(head);
            while (!queue.isEmpty()){
                Node poll = queue.poll();
                System.out.println(poll);
                if(poll.left != null)
                    queue.add(poll.left);
                if(poll.right != null)
                    queue.add(poll.right);
            }
        }

        //二叉树最大层节点数（使用map记录节点的层号）
        public static int maxWidthUseMap(Node head) {
            if(head == null)
                return 0;
            Queue<Node> queue = new LinkedList<>();
            queue.add(head);
            int curLevel  = 1;
            int curLevelNode = 0;
            int max = 0;
            HashMap<Node, Integer> map = new HashMap<>();
            map.put(head, 1);
            while(!queue.isEmpty()){
                Node cur = queue.poll();
                int curNodeLevel = map.get(cur);
                if(cur.left != null){
                    queue.add(cur.left);
                    map.put(cur.left, curNodeLevel+1);
                }
                if(cur.right != null){
                    queue.add(cur.right);
                    map.put(cur.right, curNodeLevel+1);
                }
                if(curNodeLevel == curLevel){
                    curLevelNode++;
                }else{
                    max = Math.max(curLevelNode, max);
                    curLevelNode = 1;
                    curLevel++;
                }
            }
            max = Math.max(curLevelNode, max);
            return max;
        }

        //二叉树最大层节点数（不用map记录，不考虑层号，使用变量记录最后节点的位置）
        public static int maxWidthNoMap(Node head) {
            if(head == null)
                return 0;
            Queue<Node> queue = new LinkedList<>();
            Node curEnd = head;
            Node nextEnd = null;
            queue.add(head);
            int max = 0;
            int curLevelNodes = 0;
            while(!queue.isEmpty()){
                Node poll = queue.poll();
                if(poll.left != null){
                    queue.add(poll.left);
                    nextEnd = poll.left;
                }
                if(poll.right != null){
                    queue.add(poll.right);
                    nextEnd = poll.right;
                }
                curLevelNodes++;
                if(curEnd == poll){
                    max = Math.max(max, curLevelNodes);
                    curLevelNodes = 0;
                    curEnd = nextEnd;
                }
            }
            return max;
        }

        //先序遍历序列化
        public static Queue<String> preSerial(Node head) {
            Queue<String> queue = new LinkedList<>();
            pres(head, queue);
            return queue;
        }

        public static void pres(Node head, Queue<String> ans) {
            if(head == null){
                ans.add(null);
                return;
            }
            ans.add(String.valueOf(head.value));
            pres(head.left, ans);
            pres(head.right, ans);
        }

        public static Node buildByPreQueue(Queue<String> prelist) {
            if(prelist == null || prelist.isEmpty()){
                return null;
            }
            Node preb = preb(prelist);
            return preb;
        }

        public static Node preb(Queue<String> prelist){
            String poll = prelist.poll();
            if(poll == null)
                return null;
            Node node = new Node(Integer.valueOf(poll));
            node.left = preb(prelist);
            node.right = preb(prelist);
            return node;
        }

        public static Queue<String> levelSerial(Node head) {
            if(head == null)
                return null;
            Queue<Node> queue = new LinkedList<>();
            Queue<String> ans = new LinkedList<>();
            queue.add(head);
            ans.add(String.valueOf(head.value));
            while(!queue.isEmpty()){
                Node poll = queue.poll();
                if(poll.left != null){
                    queue.add(poll.left);
                }
                if(poll.right !=null){
                    queue.add(poll.right);
                }
                ans.add(String.valueOf(poll.left));
                ans.add(String.valueOf(poll.right));
            }
            return ans;
        }

        public static Node buildByLevelQueue(Queue<String> levelList) {
            if(levelList == null || levelList.isEmpty())
                return null;
            String poll = levelList.poll();
            Node head = generateNode(poll);
            Queue<Node> queue = new LinkedList<>();
            queue.add(head);
            while(!queue.isEmpty()){
                Node node = queue.poll();
                node.left = generateNode(levelList.poll());
                node.right = generateNode(levelList.poll());
                if(node.left != null)
                    queue.add(node.left);
                if(node.right != null)
                    queue.add(node.right);
            }
            return head;
        }

        public static Node generateNode(String val) {
            if(val == null)
                return null;
            return new Node(Integer.valueOf(val));
        }
    }

    public static Node getSuccessorNode(Node node) {
        if(node == null)
            return null;
        if(node.right != null){
            Node head_right = node.right;
            while(head_right.left != null)
                head_right = head_right.left;
            return head_right;
        }else{
            Node parent = node.parent;
            while(parent != null && parent.left != node){
                node = parent;
                parent = parent.parent;
            }
            return parent;
        }
    }


    public static void printAllFlods(int N){
        printPaperProcess(1, N, true);
    }

    public static void printPaperProcess(int i, int N, boolean down) {
        if(i > N)
            return;
        printPaperProcess(i+1, N, true);
        System.out.println(down ? "凹": "凸");
        printPaperProcess(i+1, N, false);

    }


    //for test
    public static Node generateRandomBST(int maxLevel, int maxValue) {
        return generate(1, maxLevel, maxValue);
    }

    // for test
    public static Node generate(int level, int maxLevel, int maxValue) {
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }
        Node head = new Node((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }


    public static void main(String[] args) {

//        Node head = new Node(1);
//        head.left = new Node(2);
//        head.right = new Node(3);
//        head.left.left = new Node(4);
//        head.left.right = new Node(5);
//        head.right.left = new Node(6);
//        head.right.right = new Node(7);

//        Node.pre(head);
//        System.out.println("========");
//        Node.pre2(head);
//        Node.in(head);
//        System.out.println("========");
//        Node.in3(head);
//        Node.pos(head);
//        System.out.println("========");
//        Node.pos3(head);

//        int maxLevel = 10;
//        int maxValue = 100;
//        int testTimes = 1000000;
//        for (int i = 0; i < testTimes; i++) {
//            Node head = generateRandomBST(maxLevel, maxValue);
//            if (Node.maxWidthUseMap(head) != Node.maxWidthNoMap(head)) {
//                System.out.println("Oops!");
//            }
//        }
//        System.out.println("finish!");

//        Node head = new Node(6);
//        head.parent = null;
//        head.left = new Node(3);
//        head.left.parent = head;
//        head.left.left = new Node(1);
//        head.left.left.parent = head.left;
//        head.left.left.right = new Node(2);
//        head.left.left.right.parent = head.left.left;
//        head.left.right = new Node(4);
//        head.left.right.parent = head.left;
//        head.left.right.right = new Node(5);
//        head.left.right.right.parent = head.left.right;
//        head.right = new Node(9);
//        head.right.parent = head;
//        head.right.left = new Node(8);
//        head.right.left.parent = head.right;
//        head.right.left.left = new Node(7);
//        head.right.left.left.parent = head.right.left;
//        head.right.right = new Node(10);
//        head.right.right.parent = head.right;
//
//        Node test = head.left.left;
//        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
//        test = head.left.left.right;
//        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
//        test = head.left;
//        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
//        test = head.left.right;
//        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
//        test = head.left.right.right;
//        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
//        test = head;
//        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
//        test = head.right.left.left;
//        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
//        test = head.right.left;
//        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
//        test = head.right;
//        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
//        test = head.right.right; // 10's next is null
//        System.out.println(test.value + " next: " + getSuccessorNode(test));


//        int N = 3;
//        printAllFlods(3);
    }
}
